#ifndef SL_SKIPLIST_H
#define SL_SKIPLIST_H


#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <fstream>
#include <mutex>
#include <ctime>
#include "random.h"

//#define MAX_LEVEL 16 
#define FILE_NAME "datafile"

std::mutex mtx;
std::string delimiter = ":";

//节点
template<typename K, typename V>
class SkipNode {
public:
    SkipNode() {}
    SkipNode(K k, V v, int l);
    ~SkipNode();

    V get_data() const;
    K get_key() const;
    void set_data(V v);
    //void set_level(int l);
    SkipNode<K,V> **forward; //前进指针

private:
    K key;
    V value;
    int node_level;
};
//跳表
template <typename K, typename V>
class SkipList {
public:
    SkipList(int max_level);
    ~SkipList();

    bool insert(K k, V v);
    SkipNode<K, V>* create_node(K k, V v, int level);
    SkipNode<K, V>* search(K k) const;
    bool remove(K k);
    int getRandomLevel();
    void dump_file();
    void load_file();
    int get_count();
    void printList();

private:
    void get_key_value_from_string(const std::string& str, std::string* key, std::string* value); //获取键值
    bool is_valid_string(const std::string& str); //格式是否正确
    
    SkipNode<K, V> *header;
    int skiplist_level;
    int max_level;
    int element_count;
    std::ofstream file_writer;
    std::ifstream file_reader;
    Random rnd;
};

template<typename K, typename V> 
SkipNode<K,V>::SkipNode(const K k, const V v, int level){
    key = k;
    value = v;
    node_level = level;
    forward = new SkipNode<K, V>*[level+1];
    memset(forward, 0, sizeof(SkipNode<K, V>*)*(level+1));
};

template<typename K, typename V> 
SkipNode<K, V>::~SkipNode() {
    delete []forward;
};

template<typename K, typename V> 
K SkipNode<K, V>::get_key() const {
    return key;
};

template<typename K, typename V> 
V SkipNode<K, V>::get_data() const {
    return value;
};

template<typename K, typename V> 
void SkipNode<K, V>::set_data(V value) {
    this->value = value;
};
//-------------------------------------------------
//构造
template<typename K, typename V> 
SkipList<K, V>::SkipList(int max_level) : rnd(time(0)), max_level(max_level), element_count(0), skiplist_level(0){

    K k;
    V v;
    this->header = new SkipNode<K, V>(k, v, max_level); //创建头结点
};

//析构
template<typename K, typename V> 
SkipList<K, V>::~SkipList() {
    if (file_writer.is_open()) file_writer.close();
    if (file_reader.is_open()) file_reader.close();
    delete header; //删除头结点
}
//创建节点
template<typename K, typename V>
SkipNode<K, V>* SkipList<K, V>::create_node(const K k, const V v, int level) {
    SkipNode<K, V> *n = new SkipNode<K, V>(k, v, level);
    return n;
}
//插入
template<typename K, typename V>
bool SkipList<K, V>::insert(const K key, const V value) {
    mtx.lock();
    SkipNode<K, V> *current = this->header; //指向头结点
    SkipNode<K, V> *update[max_level+1]; //保存每层指向新节点的节点
    memset(update, 0, sizeof(SkipNode<K, V>*)*(max_level+1));  
    //逐层寻找插入位置
    for(int i = skiplist_level; i >= 0; --i) {
        while(current->forward[i] != NULL && current->forward[i]->get_key() < key) {
            current = current->forward[i]; 
        }
        update[i] = current;
    }
    //插入位置的后一个节点
    current = current->forward[0];

    if (current != NULL && current->get_key() == key) { //后一个节点key可能大于等于，判断key是否重复，
        std::cout << "key: " << key << " 已经存在" << std::endl;
        mtx.unlock();
        return false;
    }

    if (current == NULL || current->get_key() != key ) { //插最后面或key不重复
        
        int random_level = getRandomLevel();
        if (random_level > skiplist_level) { //超出当前层高
            for (int i = skiplist_level+1; i < random_level+1; i++) {
                update[i] = header;
            }
            skiplist_level = random_level;
        }
        SkipNode<K, V>* inserted_node = create_node(key, value, random_level);
        //插入节点
        for (int i = 0; i <= random_level; i++) {
            inserted_node->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = inserted_node;
        }
        std::cout << "key:" << key << ", value:" << value << "插入成功" << std::endl;
        element_count ++;
    }
    mtx.unlock();
    return true;
}
//获取随机level
template<typename K, typename V>
int SkipList<K, V>::getRandomLevel() {
    int level = static_cast<int>(rnd.Uniform(max_level));
    if (level == 0) {
        level = 1;
    }
    return level;
}

//打印跳表
template<typename K, typename V> 
void SkipList<K, V>::printList() {

    std::cout << "\n========SkipList========\n"; 
    for (int i = 0; i <= skiplist_level; i++) {
        SkipNode<K, V> *node = this->header->forward[i]; 
        std::cout << "Level " << i << ": ";
        while (node != NULL) {
            std::cout << node->get_key() << ":" << node->get_data() << ";";
            node = node->forward[i];
        }
        std::cout << std::endl;
    }
}

//存储到文件
template<typename K, typename V> 
void SkipList<K, V>::dump_file() {

    std::cout << ">>>>>>>>>>存储数据<<<<<<<<<<" << std::endl;
    file_writer.open(FILE_NAME);
    //第零层就是所有元素
    SkipNode<K, V> *node = this->header->forward[0]; 
    while (node != NULL) {
        file_writer << node->get_key() << ":" << node->get_data() << "\n";
        std::cout << node->get_key() << ":" << node->get_data() << ";\n";
        node = node->forward[0];
    }

    file_writer.flush();
    file_writer.close();

    return ;
}

//加载文件
template<typename K, typename V> 
void SkipList<K, V>::load_file() {

    file_reader.open(FILE_NAME);
    std::cout << ">>>>>>>>>>加载数据<<<<<<<<<<" << std::endl;
    std::string line;
    std::string* key = new std::string();
    std::string* value = new std::string();
    while (getline(file_reader, line)) {
        get_key_value_from_string(line, key, value);
        if (key->empty() || value->empty()) {
            continue;
        }
        insert(std::stoi(*key), *value);
        std::cout << "key:" << *key << "value:" << *value << std::endl;
    }
    delete key;
    delete value;
    file_reader.close();
}

//从字符串中提取键值对
template<typename K, typename V>
void SkipList<K, V>::get_key_value_from_string(const std::string& str, std::string* key, std::string* value) {

    if(!is_valid_string(str)) {
        return;
    }
    *key = str.substr(0, str.find(delimiter));
    *value = str.substr(str.find(delimiter)+1, str.length());
}

//检查字符串格式是否正确
template<typename K, typename V>
bool SkipList<K, V>::is_valid_string(const std::string& str) {

    if (str.empty()) { //空字符串
        return false;
    }
    if (str.find(delimiter) == std::string::npos) { //不存在分隔符
        return false;
    }
    return true;
}

// 获取当前元素个数
template<typename K, typename V> 
int SkipList<K, V>::get_count() { 
    return element_count;
}

//删除元素
template<typename K, typename V> 
bool SkipList<K, V>::remove(K key) {

    mtx.lock();
    SkipNode<K, V> *current = this->header; 
    SkipNode<K, V> *update[max_level+1];
    memset(update, 0, sizeof(SkipNode<K, V>*)*(max_level+1));
    //找元素位置
    for (int i = skiplist_level; i >= 0; --i) {
        while (current->forward[i] !=NULL && current->forward[i]->get_key() < key) {
            current = current->forward[i];
        }
        update[i] = current;
    }
    //找到要删除元素的位置
    current = current->forward[0];
    //如果结点不存在就返回false
    if (current == NULL || current->get_key() != key) {
        std::cout << "key:" << key << "不存在" << std::endl;
        return false;
    }
    else {
        //逐层删除节点
        for (int i = 0; i <= skiplist_level; i++) {
            //超出该节点的level
            if (update[i]->forward[i] != current) 
                break;
            update[i]->forward[i] = current->forward[i];
        }

        // 删除无节点的层
        while (skiplist_level > 0 && header->forward[skiplist_level] == 0) {
            skiplist_level --; 
        }

        std::cout << "删除成功"<< key << std::endl;
        delete current;
        element_count --;
    }
    mtx.unlock();
    return true;
}

//查找
template<typename K, typename V> 
SkipNode<K, V> * SkipList<K, V>::search(const K key) const{

    SkipNode<K, V> *current = header;

    for (int i = skiplist_level; i >= 0; i--) {
        while (current->forward[i] && current->forward[i]->get_key() < key) {
            current = current->forward[i];
        }
    }
    current = current->forward[0];

    if (current != NULL && current->get_key() == key) {
        std::cout << "找到key: " << key << ", value: " << current->get_data() << std::endl;
        return current;
    }

    std::cout << "没找到key:" << key << std::endl;
    return nullptr;
}


#endif